home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Applications / BYacc-CW 1.9 / lalr.c < prev    next >
C/C++ Source or Header  |  1995-05-20  |  10KB  |  628 lines
  1. #include "defs.h"
  2.  
  3. typedef
  4.   struct shorts
  5.     {
  6.       struct shorts *next;
  7.       short value;
  8.     }
  9.   shorts;
  10.  
  11. int tokensetsize;
  12. short *lookaheads;
  13. short *LAruleno;
  14. unsigned *LA;
  15. short *accessing_symbol;
  16. core **state_table;
  17. shifts **shift_table;
  18. reductions **reduction_table;
  19. short *goto_map;
  20. short *from_state;
  21. short *to_state;
  22.  
  23. short **transpose();
  24.  
  25. static int infinity;
  26. static int maxrhs;
  27. static int ngotos;
  28. static unsigned *F;
  29. static short **includes;
  30. static shorts **lookback;
  31. static short **R;
  32. static short *INDEX;
  33. static short *VERTICES;
  34. static int top;
  35.  
  36. static void set_state_table(void)
  37. {
  38.     register core *sp;
  39.  
  40.     state_table = NEW2(nstates, core *);
  41.     for (sp = first_state; sp; sp = sp->next)
  42.     state_table[sp->number] = sp;
  43. }
  44.  
  45.  
  46.  
  47. static void set_accessing_symbol(void)
  48. {
  49.     register core *sp;
  50.  
  51.     accessing_symbol = NEW2(nstates, short);
  52.     for (sp = first_state; sp; sp = sp->next)
  53.     accessing_symbol[sp->number] = sp->accessing_symbol;
  54. }
  55.  
  56.  
  57.  
  58. static void set_shift_table(void)
  59. {
  60.     register shifts *sp;
  61.  
  62.     shift_table = NEW2(nstates, shifts *);
  63.     for (sp = first_shift; sp; sp = sp->next)
  64.     shift_table[sp->number] = sp;
  65. }
  66.  
  67.  
  68.  
  69. static void set_reduction_table(void)
  70. {
  71.     register reductions *rp;
  72.  
  73.     reduction_table = NEW2(nstates, reductions *);
  74.     for (rp = first_reduction; rp; rp = rp->next)
  75.     reduction_table[rp->number] = rp;
  76. }
  77.  
  78.  
  79.  
  80. static void set_maxrhs(void)
  81. {
  82.   register short *itemp;
  83.   register short *item_end;
  84.   register int length;
  85.   register int max;
  86.  
  87.   length = 0;
  88.   max = 0;
  89.   item_end = ritem + nitems;
  90.   for (itemp = ritem; itemp < item_end; itemp++)
  91.     {
  92.       if (*itemp >= 0)
  93.     {
  94.       length++;
  95.     }
  96.       else
  97.     {
  98.       if (length > max) max = length;
  99.       length = 0;
  100.     }
  101.     }
  102.  
  103.   maxrhs = max;
  104. }
  105.  
  106.  
  107.  
  108. static void initialize_LA(void)
  109. {
  110.   register int i, j, k;
  111.   register reductions *rp;
  112.  
  113.   lookaheads = NEW2(nstates + 1, short);
  114.  
  115.   k = 0;
  116.   for (i = 0; i < nstates; i++)
  117.     {
  118.       lookaheads[i] = k;
  119.       rp = reduction_table[i];
  120.       if (rp)
  121.     k += rp->nreds;
  122.     }
  123.   lookaheads[nstates] = k;
  124.  
  125.   LA = NEW2(k * tokensetsize, unsigned);
  126.   LAruleno = NEW2(k, short);
  127.   lookback = NEW2(k, shorts *);
  128.  
  129.   k = 0;
  130.   for (i = 0; i < nstates; i++)
  131.     {
  132.       rp = reduction_table[i];
  133.       if (rp)
  134.     {
  135.       for (j = 0; j < rp->nreds; j++)
  136.         {
  137.           LAruleno[k] = rp->rules[j];
  138.           k++;
  139.         }
  140.     }
  141.     }
  142. }
  143.  
  144.  
  145. static void set_goto_map(void)
  146. {
  147.   register shifts *sp;
  148.   register int i;
  149.   register int symbol;
  150.   register int k;
  151.   register short *temp_map;
  152.   register int state2;
  153.   register int state1;
  154.  
  155.   goto_map = NEW2(nvars + 1, short) - ntokens;
  156.   temp_map = NEW2(nvars + 1, short) - ntokens;
  157.  
  158.   ngotos = 0;
  159.   for (sp = first_shift; sp; sp = sp->next)
  160.     {
  161.       for (i = sp->nshifts - 1; i >= 0; i--)
  162.     {
  163.       symbol = accessing_symbol[sp->shift[i]];
  164.  
  165.       if (ISTOKEN(symbol)) break;
  166.  
  167.       if (ngotos == MAXSHORT)
  168.         fatal("too many gotos");
  169.  
  170.       ngotos++;
  171.       goto_map[symbol]++;
  172.         }
  173.     }
  174.  
  175.   k = 0;
  176.   for (i = ntokens; i < nsyms; i++)
  177.     {
  178.       temp_map[i] = k;
  179.       k += goto_map[i];
  180.     }
  181.  
  182.   for (i = ntokens; i < nsyms; i++)
  183.     goto_map[i] = temp_map[i];
  184.  
  185.   goto_map[nsyms] = ngotos;
  186.   temp_map[nsyms] = ngotos;
  187.  
  188.   from_state = NEW2(ngotos, short);
  189.   to_state = NEW2(ngotos, short);
  190.  
  191.   for (sp = first_shift; sp; sp = sp->next)
  192.     {
  193.       state1 = sp->number;
  194.       for (i = sp->nshifts - 1; i >= 0; i--)
  195.     {
  196.       state2 = sp->shift[i];
  197.       symbol = accessing_symbol[state2];
  198.  
  199.       if (ISTOKEN(symbol)) break;
  200.  
  201.       k = temp_map[symbol]++;
  202.       from_state[k] = state1;
  203.       to_state[k] = state2;
  204.     }
  205.     }
  206.  
  207.   FREE(temp_map + ntokens);
  208. }
  209.  
  210.  
  211.  
  212. /*  Map_goto maps a state/symbol pair into its numeric representation.    */
  213.  
  214. static int map_goto(int state, int symbol)
  215. {
  216.     register int high;
  217.     register int low;
  218.     register int middle;
  219.     register int s;
  220.  
  221.     low = goto_map[symbol];
  222.     high = goto_map[symbol + 1];
  223.  
  224.     for (;;)
  225.     {
  226.     assert(low <= high);
  227.     middle = (low + high) >> 1;
  228.     s = from_state[middle];
  229.     if (s == state)
  230.         return (middle);
  231.     else if (s < state)
  232.         low = middle + 1;
  233.     else
  234.         high = middle - 1;
  235.     }
  236. }
  237.  
  238.  
  239.  
  240. static void traverse(register int i)
  241. {
  242.   register unsigned *fp1;
  243.   register unsigned *fp2;
  244.   register unsigned *fp3;
  245.   register int j;
  246.   register short *rp;
  247.  
  248.   int height;
  249.   unsigned *base;
  250.  
  251.   VERTICES[++top] = i;
  252.   INDEX[i] = height = top;
  253.  
  254.   base = F + i * tokensetsize;
  255.   fp3 = base + tokensetsize;
  256.  
  257.   rp = R[i];
  258.   if (rp)
  259.     {
  260.       while ((j = *rp++) >= 0)
  261.     {
  262.       if (INDEX[j] == 0)
  263.         traverse(j);
  264.  
  265.       if (INDEX[i] > INDEX[j])
  266.         INDEX[i] = INDEX[j];
  267.  
  268.       fp1 = base;
  269.       fp2 = F + j * tokensetsize;
  270.  
  271.       while (fp1 < fp3)
  272.         *fp1++ |= *fp2++;
  273.     }
  274.     }
  275.  
  276.   if (INDEX[i] == height)
  277.     {
  278.       for (;;)
  279.     {
  280.       j = VERTICES[top--];
  281.       INDEX[j] = infinity;
  282.  
  283.       if (i == j)
  284.         break;
  285.  
  286.       fp1 = base;
  287.       fp2 = F + j * tokensetsize;
  288.  
  289.       while (fp1 < fp3)
  290.         *fp2++ = *fp1++;
  291.     }
  292.     }
  293. }
  294.  
  295.  
  296. static void digraph(short **relation)
  297. {
  298.   register int i;
  299.  
  300.   infinity = ngotos + 2;
  301.   INDEX = NEW2(ngotos + 1, short);
  302.   VERTICES = NEW2(ngotos + 1, short);
  303.   top = 0;
  304.  
  305.   R = relation;
  306.  
  307.   for (i = 0; i < ngotos; i++)
  308.     INDEX[i] = 0;
  309.  
  310.   for (i = 0; i < ngotos; i++)
  311.     {
  312.       if (INDEX[i] == 0 && R[i])
  313.     traverse(i);
  314.     }
  315.  
  316.   FREE(INDEX);
  317.   FREE(VERTICES);
  318. }
  319.  
  320.  
  321. static void initialize_F(void)
  322. {
  323.   register int i;
  324.   register int j;
  325.   register int k;
  326.   register shifts *sp;
  327.   register short *edge;
  328.   register unsigned *rowp;
  329.   register short *rp;
  330.   register short **reads;
  331.   register int nedges;
  332.   register int stateno;
  333.   register int symbol;
  334.   register int nwords;
  335.  
  336.   nwords = ngotos * tokensetsize;
  337.   F = NEW2(nwords, unsigned);
  338.  
  339.   reads = NEW2(ngotos, short *);
  340.   edge = NEW2(ngotos + 1, short);
  341.   nedges = 0;
  342.  
  343.   rowp = F;
  344.   for (i = 0; i < ngotos; i++)
  345.     {
  346.       stateno = to_state[i];
  347.       sp = shift_table[stateno];
  348.  
  349.       if (sp)
  350.     {
  351.       k = sp->nshifts;
  352.  
  353.       for (j = 0; j < k; j++)
  354.         {
  355.           symbol = accessing_symbol[sp->shift[j]];
  356.           if (ISVAR(symbol))
  357.         break;
  358.           SETBIT(rowp, symbol);
  359.         }
  360.  
  361.       for (; j < k; j++)
  362.         {
  363.           symbol = accessing_symbol[sp->shift[j]];
  364.           if (nullable[symbol])
  365.         edge[nedges++] = map_goto(stateno, symbol);
  366.         }
  367.     
  368.       if (nedges)
  369.         {
  370.           reads[i] = rp = NEW2(nedges + 1, short);
  371.  
  372.           for (j = 0; j < nedges; j++)
  373.         rp[j] = edge[j];
  374.  
  375.           rp[nedges] = -1;
  376.           nedges = 0;
  377.         }
  378.     }
  379.  
  380.       rowp += tokensetsize;
  381.     }
  382.  
  383.   SETBIT(F, 0);
  384.   digraph(reads);
  385.  
  386.   for (i = 0; i < ngotos; i++)
  387.     {
  388.       if (reads[i])
  389.     FREE(reads[i]);
  390.     }
  391.  
  392.   FREE(reads);
  393.   FREE(edge);
  394. }
  395.  
  396.  
  397. static void add_lookback_edge(int stateno, int ruleno, int gotono)
  398. {
  399.     register int i, k;
  400.     register int found;
  401.     register shorts *sp;
  402.  
  403.     i = lookaheads[stateno];
  404.     k = lookaheads[stateno + 1];
  405.     found = 0;
  406.     while (!found && i < k)
  407.     {
  408.     if (LAruleno[i] == ruleno)
  409.         found = 1;
  410.     else
  411.         ++i;
  412.     }
  413.     assert(found);
  414.  
  415.     sp = NEW(shorts);
  416.     sp->next = lookback[i];
  417.     sp->value = gotono;
  418.     lookback[i] = sp;
  419. }
  420.  
  421.  
  422. static void build_relations(void)
  423. {
  424.   register int i;
  425.   register int j;
  426.   register int k;
  427.   register short *rulep;
  428.   register short *rp;
  429.   register shifts *sp;
  430.   register int length;
  431.   register int nedges;
  432.   register int done;
  433.   register int state1;
  434.   register int stateno;
  435.   register int symbol1;
  436.   register int symbol2;
  437.   register short *shortp;
  438.   register short *edge;
  439.   register short *states;
  440.   register short **new_includes;
  441.  
  442.   includes = NEW2(ngotos, short *);
  443.   edge = NEW2(ngotos + 1, short);
  444.   states = NEW2(maxrhs + 1, short);
  445.  
  446.   for (i = 0; i < ngotos; i++)
  447.     {
  448.       nedges = 0;
  449.       state1 = from_state[i];
  450.       symbol1 = accessing_symbol[to_state[i]];
  451.  
  452.       for (rulep = derives[symbol1]; *rulep >= 0; rulep++)
  453.     {
  454.       length = 1;
  455.       states[0] = state1;
  456.       stateno = state1;
  457.  
  458.       for (rp = ritem + rrhs[*rulep]; *rp >= 0; rp++)
  459.         {
  460.           symbol2 = *rp;
  461.           sp = shift_table[stateno];
  462.           k = sp->nshifts;
  463.  
  464.           for (j = 0; j < k; j++)
  465.         {
  466.           stateno = sp->shift[j];
  467.           if (accessing_symbol[stateno] == symbol2) break;
  468.         }
  469.  
  470.           states[length++] = stateno;
  471.         }
  472.  
  473.       add_lookback_edge(stateno, *rulep, i);
  474.  
  475.       length--;
  476.       done = 0;
  477.       while (!done)
  478.         {
  479.           done = 1;
  480.           rp--;
  481.           if (ISVAR(*rp))
  482.         {
  483.           stateno = states[--length];
  484.           edge[nedges++] = map_goto(stateno, *rp);
  485.           if (nullable[*rp] && length > 0) done = 0;
  486.         }
  487.         }
  488.     }
  489.  
  490.       if (nedges)
  491.     {
  492.       includes[i] = shortp = NEW2(nedges + 1, short);
  493.       for (j = 0; j < nedges; j++)
  494.         shortp[j] = edge[j];
  495.       shortp[nedges] = -1;
  496.     }
  497.     }
  498.  
  499.   new_includes = transpose(includes, ngotos);
  500.  
  501.   for (i = 0; i < ngotos; i++)
  502.     if (includes[i])
  503.       FREE(includes[i]);
  504.  
  505.   FREE(includes);
  506.  
  507.   includes = new_includes;
  508.  
  509.   FREE(edge);
  510.   FREE(states);
  511. }
  512.  
  513.  
  514. static short **transpose(short **R, int n)
  515. {
  516.   register short **new_R;
  517.   register short **temp_R;
  518.   register short *nedges;
  519.   register short *sp;
  520.   register int i;
  521.   register int k;
  522.  
  523.   nedges = NEW2(n, short);
  524.  
  525.   for (i = 0; i < n; i++)
  526.     {
  527.       sp = R[i];
  528.       if (sp)
  529.     {
  530.       while (*sp >= 0)
  531.         nedges[*sp++]++;
  532.     }
  533.     }
  534.  
  535.   new_R = NEW2(n, short *);
  536.   temp_R = NEW2(n, short *);
  537.  
  538.   for (i = 0; i < n; i++)
  539.     {
  540.       k = nedges[i];
  541.       if (k > 0)
  542.     {
  543.       sp = NEW2(k + 1, short);
  544.       new_R[i] = sp;
  545.       temp_R[i] = sp;
  546.       sp[k] = -1;
  547.     }
  548.     }
  549.  
  550.   FREE(nedges);
  551.  
  552.   for (i = 0; i < n; i++)
  553.     {
  554.       sp = R[i];
  555.       if (sp)
  556.     {
  557.       while (*sp >= 0)
  558.         *temp_R[*sp++]++ = i;
  559.     }
  560.     }
  561.  
  562.   FREE(temp_R);
  563.  
  564.   return (new_R);
  565. }
  566.  
  567.  
  568.  
  569. static void compute_FOLLOWS(void)
  570. {
  571.   digraph(includes);
  572. }
  573.  
  574.  
  575. static void compute_lookaheads(void)
  576. {
  577.   register int i, n;
  578.   register unsigned *fp1, *fp2, *fp3;
  579.   register shorts *sp, *next;
  580.   register unsigned *rowp;
  581.  
  582.   rowp = LA;
  583.   n = lookaheads[nstates];
  584.   for (i = 0; i < n; i++)
  585.     {
  586.       fp3 = rowp + tokensetsize;
  587.       for (sp = lookback[i]; sp; sp = sp->next)
  588.     {
  589.       fp1 = rowp;
  590.       fp2 = F + tokensetsize * sp->value;
  591.       while (fp1 < fp3)
  592.         *fp1++ |= *fp2++;
  593.     }
  594.       rowp = fp3;
  595.     }
  596.  
  597.   for (i = 0; i < n; i++)
  598.     for (sp = lookback[i]; sp; sp = next)
  599.       {
  600.         next = sp->next;
  601.         FREE(sp);
  602.       }
  603.  
  604.   FREE(lookback);
  605.   FREE(F);
  606. }
  607.  
  608.  
  609.  
  610. void lalr(void)
  611. {
  612.     tokensetsize = WORDSIZE(ntokens);
  613.  
  614.     set_state_table();
  615.     set_accessing_symbol();
  616.     set_shift_table();
  617.     set_reduction_table();
  618.     set_maxrhs();
  619.     initialize_LA();
  620.     set_goto_map();
  621.     initialize_F();
  622.     build_relations();
  623.     compute_FOLLOWS();
  624.     compute_lookaheads();
  625. }
  626.  
  627.  
  628.